package 图.树.树形DP;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/14 11:27
 */
public class lc979二叉树分配硬币 {

    /*
      确实不太好想啊
      这里看下灵神的思路!
      https://leetcode.cn/problems/distribute-coins-in-binary-tree/solutions/2343262/tu-jie-mei-you-si-lu-jin-lai-miao-dong-p-vrni/
      难顶!

      贡献法！


      之后也再去理解一下， 拓展题， 给出的  ** 贡献法** 题单！

     */

    // Error 不太对
    public int[] tree_dp(TreeNode node){
        if(node == null){
            return new int[]{0,0};
        }
        int[] left = tree_dp(node.left);
        int[] right = tree_dp(node.right);
        int coins = left[1] + right[1] + node.val - 1;
        int steps = Math.abs(left[0]) + Math.abs(right[0]) + node.val > 0 ? Math.abs(node.val - 1) : 1;
        return new int[]{steps,coins};
    }

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }

    }

}
